package mybs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * 组合 题目：不用递归法 求一个固定集合内的所有子集
 * 
 * 说明： 1. power set，可参考 http://en.wikipedia.org/wiki/Power_set 2.
 * 對於問題，我會問interviewer輸入集合的大小，以及輸出的方式。有些情況用stack可能比較高效。
 */
public class Combination {

	// 这个是递归实现
	// 算法：
	/*
	 * Recursive algorithm： 
	 * Power set of A{0,1,...,n} 
	 * If n = 0 return A[0]
	 * Otherwise, 
	 * generate the power set of {0,1,...,n-1} 
	 * make a new copy of each subset and adjoin the element n to it 
	 * return the set of all sets created.
	 */
	public static List<List<Integer>> findCombinations(int[] a) {
		return findCombinations(a, a.length - 1);
	}

	private static List<List<Integer>> findCombinations(int[] a, int j) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (-1 == j) {
//			List<Integer> temp1 = new ArrayList<Integer>();
//			temp1.add(a[j]);
			list.add(new ArrayList<Integer>());
			return list;
		}

		List<List<Integer>> result = findCombinations(a, j - 1);

		list.addAll(result);
		List<Integer> temp1 = new ArrayList<Integer>();
		temp1.add(a[j]);
		list.add(temp1);
		for (List<Integer> t : result) {
			if(t.size()==0)
				continue;
			List<Integer> temp = new ArrayList<Integer>();
			temp.add(a[j]);
			temp.addAll(t);
			list.add(temp);
		}
		return list;
	}

	// 非递归实现
	// 来自: http://www.koders.com/java/fidAD43F65D67DC8A5E4086DB82B622EE88B4DC2D0C.aspx
	public static <T extends Comparable<? super T>> List<List<T>> findCombinations(
			Collection<T> elements) {
		List<List<T>> result = new ArrayList<List<T>>();

		for (int i = 0; i <= elements.size(); i++)
			result.addAll(findCombinations(elements, i));

		return result;
	}
	
	// C(i/n)
	public static <T extends Comparable<? super T>> List<List<T>> findCombinations(
			Collection<T> elements, int n) {
		List<List<T>> result = new ArrayList<List<T>>();

		if (n == 0) {
			result.add(new ArrayList<T>());

			return result;
		}

		List<List<T>> combinations = findCombinations(elements, n - 1);
		for (List<T> combination : combinations) {
			for (T element : elements) {
				if (combination.contains(element)) {
					continue;
				}

				List<T> list = new ArrayList<T>();

				list.addAll(combination);

				if (list.contains(element))
					continue;

				list.add(element);
				Collections.sort(list);

				if (result.contains(list))
					continue;

				result.add(list);
			}
		}

		return result;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 1, 2, 3,4};

		System.out.println(Combination.findCombinations(a));

	}

}
